"""
doc string comes here
"""

from math import log
from random import randint as randi
from random import random
from random import uniform as rand
from numpy import shape

algorithmSettings = {'chromosomeLength' : [3],
                     'populationSize' : 10,
                     'iterations' : 200000,
                     'crossoverRate' : 0.8,
                     'mutationRate' : 0.05, 
                     'integerProblem' : 'Yes', 
                     'state':'maximize'}

searchSpace = '0,7;0,7'
negativeValues = []

def setChromosomeLength(searchSpace):
    searchSpace = [float(endPoint) for varLimits in searchSpace.split(';') for endPoint in varLimits.split(',')]

    chromosomeLength = []
    for varPointer in range(0,  len(searchSpace), 2):
        lBound = min(searchSpace[varPointer], searchSpace[varPointer+1])
        uBound = max(searchSpace[varPointer], searchSpace[varPointer+1])
        
        isNegative = 0
    
        if lBound<0:
            isNegative = 1
            negativeValues.append('Yes')
        if lBound >=0:
            negativeValues.append('No')
        if lBound ==float('-inf') or uBound == float('inf'):
            chromosomeLength.append(32 + 1*isNegative)
            continue
    
        chromosomeLength.append(int(log(max(abs(lBound), abs(uBound)),  2) + 1 + 1*isNegative))
    
    algorithmSettings['chromosomeLength'] = chromosomeLength


def initChromosome():
    chromosome = [randi(0,1) for i in range(sum(algorithmSettings['chromosomeLength']))]
    return chromosome

def initPopulation():
    population = []
    for member in range(algorithmSettings['populationSize']):
        population.append(initChromosome())
    return population

def crossover(population):
    shouldCrossover = random()
    if shouldCrossover <= algorithmSettings['crossoverRate']:
        crossoverPoint = randi(0,shape(population)[1]-1)
        for i in range(0,shape(population)[0]-1,2):
            (population[i])[0:crossoverPoint], (population[i+1])[0:crossoverPoint] = (population[i+1])[0:crossoverPoint], (population[i])[0:crossoverPoint]
    return population

def mutate(population):
    shouldMutate = random()
    if shouldMutate <= algorithmSettings['mutationRate']:
        mutateMember = randi(0,shape(population)[0]-1)
        mutateBit = randi(0,shape(population)[1]-1)
        population[mutateMember][mutateBit] = ((population[mutateMember][mutateBit])+1)%2
    return population

def splitMember(member,  chromosomeLength):
    splittedMember = []
    start = 0
    for cLength in chromosomeLength:
        end = start+ cLength
        currentGCode = member[start:end]
        bitString = ''
        for bit in currentGCode:
            bitString += str(bit)
        splittedMember.append(bitString)
        start = end 
    return splittedMember

def evaluateVariableValues(population):
    chromosomeLength = algorithmSettings['chromosomeLength']
    values = []
    for member in population:
        memberValues = []
        variableGCodes = splitMember(member,  chromosomeLength)
        variableIndex = 0
        for bitString in variableGCodes:
            if negativeValues[variableIndex] == 'Yes':
                memberValues.append((int(bitString[1:],  2)) * ((-1)**int(bitString[0])))
            else:
                memberValues.append(int(bitString,  2))
            variableIndex += 1
        values.append(memberValues)
    return values

def normalizeFitness(fitnessValues):
    fitnessMax = max(fitnessValues)
    fitnessMin = min(fitnessValues)
    
    newFitness = [1+fitness+abs(fitnessMin) for fitness in fitnessValues]
    fitnessValues = [float(fitness)*100/max(newFitness) for fitness in newFitness]
    return fitnessValues

def evaluateFitness(population,  objectiveFunctions,  constraintFunctions,  variables):
    varValues = evaluateVariableValues(population)
    fitnessValues = []
    memberCount = 0
    for member in population:
        parameterValues = {}
        for value, symbol in zip(varValues[memberCount],  variables):
            parameterValues[symbol] = value
        
        fitness = eval(objectiveFunctions,  parameterValues)
        
        for function in constraintFunctions:
            if not eval(function,  parameterValues):
#                print function,  'violated since '
#                print parameterValues.values(),  parameterValues.keys()
                if algorithmSettings['state'] =='maximize':
                    fitness -= 10000
                else:
                    fitness += 10000
            #print 'Constraint "' + function + '" violated'
        
        fitnessValues.append(fitness)
        memberCount += 1
        normalizedFitnessValues = normalizeFitness(fitnessValues)
    return normalizedFitnessValues
    
def sortChromosomes(population,  fitnessValues):
    augmentedChromosome = {}
    for member, value in zip(population,  fitnessValues):
        augmentedChromosome[value] = member
        #print type(augmentedChromosome)
    #print augmentedChromosome
    return augmentedChromosome.values()

def rouletteWheel(population,  fitnessValues):
    
    """ Courtesy : http://stackoverflow.com/questions/177271/roulette-selection-in-genetic-algorithms - C Code """
    #print "Input population is:"
    #print population
    #print "And their corresponding fitness values are:"
    #print fitnessValues
    
    n = len(fitnessValues)
    #print n
    avgFitness = [float(fitness)/sum(fitnessValues) for fitness in fitnessValues]
    
    reproductionPool = []
    for member in range(n):
        probability = rand(0, 1)
        memberID = 0
        partialSum = 0
        
        while probability > partialSum:
            partialSum += avgFitness[memberID]
            memberID +=1
            if memberID >= algorithmSettings['populationSize']:
                memberID = algorithmSettings['populationSize']-1
        #print memberID,  'chosen'
        reproductionPool.append(population[memberID])
        #print reproductionPool
    return reproductionPool
        

def optimize(variables,  objectiveFunctions,  constraintFunctions):
    output = ''
    print "Variables:"
    
    print "----------"
    for varCount in range(len(variables)):
        print '          ' + variables[varCount] 
    
    print "Objective Functions:"
    print "--------------------"
    for functionCount in range(len(objectiveFunctions)):
        print '          ' + str(functionCount+1) + '. ' + objectiveFunctions[functionCount]
    print '\n'
    
    print "Constraint Functions:"
    print "--------------------"
    for functionCount in range(len(constraintFunctions)):
        print '          ' + str(functionCount+1) + '. ' + constraintFunctions[functionCount]
    print '\n'
    
    setChromosomeLength(searchSpace)
    population = initPopulation()
    #print "Initialized Population is:"
    #print population
    
    for iterCount in range(algorithmSettings['iterations']):
        fitnessValues = evaluateFitness(population,  objectiveFunctions,  constraintFunctions,  variables)
        #population = sortChromosomes(population, fitnessValues)
        #print "Population after sorting with respect to fitness values is:"
        #print population
        population = rouletteWheel(population, fitnessValues)
        #print population
        
        if algorithmSettings['state'] == 'maximize':
            population.reverse()
        population = mutate(crossover(population))
        print population
        #print fitnessValues
    return population

if __name__ =="__main__":
    Variables = ['x','y']
    Objective = 'x+y'
    Constraints = ['x*y==16']

    searchSpace = '0,7;0,7'
    algorithmSettings['iterations'] = 1000
    algorithmSettings['populationSize'] = 20
    finalSolution =  optimize(Variables, Objective, Constraints)
    print evaluateVariableValues(finalSolution)
